package esercitazione5.graphs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


/**
 * Classe che implementa algoritmi per la visita (dfs e bfs) dei grafi.
 * Inoltre l'algoritmo bfs viene utilizzato anche per ottenere una visita ordinata (ordinamento topologico) di un grafo.
 *
 * @param <V>
 * @param <E>
 */
public class Visit<V, E> {

	// Grafo su cui si effettuano le operazioni di visita.
	private GraphInterface<V,E> g;

	/**
	 * Costruttore che inizializza il grafo 
	 * @param g
	 */
	public Visit(GraphInterface<V, E> g){
		this.g = g;
	}

	/**
	 * Algoritmo di visita in ampiezza di un grafo.
	 * @param vertex Vertice da cui partire
	 * @return
	 */
	public  List<Vertex<V>> bfs(Vertex<V> vertex){
		// Inizializzo le due strutture necessarie
		// Apertura: per contenere tutti i vertici individuati ma non espansi.
		// Chiusura: per contenere tutti i vertici già espansi.
		LinkedList<Vertex<V>> apertura = new LinkedList<Vertex<V>>();
		ArrayList<Vertex<V>> chiusura = new ArrayList<Vertex<V>>();
		
		// Aggiungo il vertice corrente.
		apertura.addLast(vertex);
		
		// Ciclo su tutti i vertici contenuti nell'apertura.
		while (!apertura.isEmpty()) {
			// Prendo il PRIMO vertice dall'apertura
			Vertex<V> curr = apertura.removeFirst();
			// Aggiungo il vertice appena prelevato alla chiusura, poichè voglio espanderlo.
			chiusura.add(curr);
			// Per tutti i vertici che posso raggiungere dal vertice corrente...
			for(Edge<V> ver : g.outgoingEdges(curr)){
				// ...se l'apertura o la chiusura non contengono già questo vertice, lo aggiungo come ULTIMO elemento dell'apertura
				if (!apertura.contains(ver.getDestination()) && !chiusura.contains(ver.getDestination()))
					apertura.addLast(ver.getDestination());
			}
			
			// Se l'apertura è vuota...
			if (apertura.isEmpty()) {
				// ...per ogni vertice del grafo...
				for(Vertex<V> v : g.vertices()){
					// ...se la chiusura non contiene questo vertice (cioè non è mai stato espanso) lo aggiungo all'apertura
					if(!chiusura.contains(v)){
						apertura.addLast(v);
						break;
					}
				}
			}
		}
		// Ritorno l'insieme di chiusura poichè, a partire dal vertice di partenza, ho visitato (e inserito nella chiusura)
		// in maniera ordinata i vertici l'albero, espandendo sempre tali vertici per interi "livelli" successivi di profondità.
		return chiusura;
	}

	// Metodo pubblico che inizializza le strutture necessarie all'algoritmo dfs prima di richiamare il metodo privato.
	// "time" è un intero arbitrario, segna il valore di inizio dell'algoritmo.
	/**
	 * inizializza le strutture necessarie all'algoritmo dfs prima di richiamare il metodo privato.
	 * @param vertex Vertice da cui partire
	 * @param time è un intero arbitrario, segna il valore di inizio dell'algoritmo.
	 * @return La lista dei vertici dopo la visita
	 */
	public  List<Vertex<V>> dfs(Vertex<V> vertex, int time){
		// Inizializzo tutti i vertici dell'albero dando a tutti il colore BIANCO
		for(Vertex<V> v : g.vertices()){
			v.addProperty("color", "white");
		}

		// Inizializzo un insieme di chiusura per i vertici già espansi.
		ArrayList<Vertex<V>> chiusura = new ArrayList<Vertex<V>>();
		// Avvio dell'algoritmo
		time = dfsVisit(vertex, chiusura, time);
		// Per ogni vertice del grafo...
		for(Vertex<V> remainder : g.vertices()){
			// ...se il vertice è ancora bianco...
			if(remainder.getProperty("color") == "white")
				// ...avvia l'algoritmo nuovamente anche su quel vertice
				time = dfsVisit(remainder, chiusura, time);
		}
		// Ritorno l'insieme di chiusura poichè, a partire dal vertice di partenza, ho visitato (e inserito nella chiusura)
		// in maniera ordinata i vertici l'albero, espandendo sempre tali vertici procedendo sempre di figlio in figlio.
		// Raggiunta un vertice senza archi uscenti, si ritorna al penultimo vertice visitato.
		return chiusura;
	}

	/**
	 * Algoritmo di visita in profondità di un grafo.
	 * Introducendo due decoratori al vertice "apertureTime" che rappresenta il tempo, inteso come iterazione,
	 * in cui il vertice viene inserito nella lista di apertura e "finishTime" che rappresenta il tempo n cui il vertice 
	 * viene inserito nella lista di chiusura e quindi processato.
	 * @param v Vertice che si sta analizzando
	 * @param chiusura Lista di chiusura
	 * @param time paramentro di tempo
	 * @return il tempo aggiornato
	 */
	private int dfsVisit(Vertex<V> v, List<Vertex<V>> chiusura, int time) {
		// Aggiungo il vertice corrente alla chiusura, poichè voglio espanderlo.
		chiusura.add(v);
		// Poichè voglio espandere il vertice, gli assegno il colore GRIGIO
		v.addProperty("color", "gray");
		// Assegno il tempo di apertura al vertice GRIGIO
		v.addProperty("apertureTime", time++);
		// Per ogni edge uscente dal vertice corrente...
		for(Edge<V> e : g.outgoingEdges(v)){
			// ...se il colore del vertice destinazione è bianco...
			if(e.getDestination().getProperty("color")=="white"){
				// ...chiamo ricorsivamente l'algoritmo con vertice corrente quello appena individuato
				time = dfsVisit(e.getDestination(), chiusura, time);
			}
		}
		// Completata la visita del vertice corrente, gli assegno il colore NERO
		v.addProperty("color", "black");
		// Assegno il tempo di chiusura al vertice NERO
		v.addProperty("finishTime", time++);
		
		// Ritorno il tempo corrente ottenuto dopo l'apertura/chiusura di tutti i vertici finora espansi.
		return time;
	}

	/**
	 * Algoritmo di visita in ordine topologico.
	 * @param v Veritice da cui partire
	 * @return Lista di vertici dopo l'ordinamento
	 */
	public List<Vertex<V>> topologicalOrder(Vertex<V> v){
		// Avvio l'algoritmo di visita in profondità sul vertice, al tempo 0.
		// Ottengo la lista dei vertici visitati dalla dfs
		List<Vertex<V>> list = dfs(v, 0);
		// Istanzio una struttura, inizialmente vuota, che conterrà poi l'ordinamento topologico
		List<Vertex<V>> orderedList = new ArrayList<Vertex<V>>();
		// Per ogni vertice ottenuto dalla dfs...
		for(Vertex<V> vertex : list){
			// ...ottengo il tempo di chiusura e lo salvo in 'value'...
			String prop = "finishTime";
			int value = (int) vertex.getProperty(prop);
			// ...se la lista ordinata topologicamente è vuota, inserisco direttamente quel vertice...
			if(orderedList.size() == 0)
				orderedList.add(vertex);
			// ...altrimenti...
			else{
				// ...per ogni vertice già presente nella lista ordinata...
				for(int i = 0; i < orderedList.size(); i++)
					// ...se 'value' è maggiore del valore di quel vertice
					if(value > (int) orderedList.get(i).getProperty(prop)){
						// ...aggiungo quel vertice alla lista in quella posizione.
						orderedList.add(i, vertex);
						break;
					}
				// se 'value' è minore di tutti gli altri già inseriti nella lista ordinata, aggiungo il vertice in coda.
				if(value < (int) orderedList.get(orderedList.size()-1).getProperty(prop))
					orderedList.add(vertex);
			}
		}
		// Ritorno la lista di tutti i vertici, in base all'ordinamento topologico.
		return orderedList;
	}

	public static void main(String[] args) {
		GraphInterface<Integer, Integer> g = new Graph<Integer, Integer>();
		Vertex<Integer> uno = g.insertVertex(1);
		Vertex<Integer> due = g.insertVertex(2);
		Vertex<Integer> tre = g.insertVertex(3);
		Vertex<Integer> quattro = g.insertVertex(4);
		Vertex<Integer> cinque = g.insertVertex(5);
		Vertex<Integer> sei = g.insertVertex(6);
		Vertex<Integer> sette = g.insertVertex(7);
		Vertex<Integer> otto = g.insertVertex(8);
		Vertex<Integer> nove = g.insertVertex(9);
		Vertex<Integer> dieci = g.insertVertex(10);
		Vertex<Integer> undici = g.insertVertex(11);

		g.insertEdge(due, tre, 1);
		g.insertEdge(due, cinque, 1);
		g.insertEdge(quattro, cinque, 1);
		g.insertEdge(quattro, dieci, 1);
		g.insertEdge(cinque, sette, 4);
		g.insertEdge(sette, uno, 1);
		g.insertEdge(sette, nove, 1);
		g.insertEdge(uno, undici, 1);
		g.insertEdge(sei, otto, 1);
		g.insertEdge(dieci, sette, 1);

		System.out.println("visita bfs:");
		Visit<Integer, Integer> v = new Visit<>(g);
		ArrayList<Vertex<Integer>> l =  (ArrayList<Vertex<Integer>>) v.bfs(tre);
		for(Vertex<Integer> vert : l){
			System.out.println(vert.getValue());
		}
		System.out.println();
		
		System.out.println("visita dfs:");
		ArrayList<Vertex<Integer>> list =  new ArrayList<>(v.dfs(due, 0)) ;
		for(Vertex<Integer> vert : list){
			System.out.println(vert.getValue()+" "+vert.getProperty("apertureTime")+"/"+vert.getProperty("finishTime"));
		}
		System.out.println();
		
		System.out.println("ordinamento topologico:");
		ArrayList<Vertex<Integer>> listOrdered =  new ArrayList<>(v.topologicalOrder(tre)) ;
		for(Vertex<Integer> vert : listOrdered){
			System.out.println(vert.getValue()+" "+vert.getProperty("apertureTime")+"/"+vert.getProperty("finishTime"));
		}
	}
}
